package com.leetcode.algorithm.common;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TreeNodeUtils {

	/**
	 * 根据leetcode二叉树的数组表示形式还原二叉树:
	 * 枝叶节点如果非空，有左右子节点
	 * 
	 * @param arr
	 * @return
	 */
	public static TreeNode convertFromArr(Integer[] arr) {
		int len = arr.length;
		if (len == 0) {
			return null;
		}
		TreeNode[] nodeArr = new TreeNode[len];
		for (int i = 0; i < len; i++) {
			if (arr[i] == null) {
				nodeArr[i] = null;
			} else {
				nodeArr[i] = new TreeNode(arr[i].intValue());
			}
		}

		// queue中存放非空的节点
		Queue<TreeNode> queue = new LinkedList<>();
		int idx = 0;
		if (nodeArr[0] != null) {
			queue.add(nodeArr[0]);
		}
		while (!queue.isEmpty() && idx < len) {
			TreeNode node = queue.poll();
			idx++;
			if (idx >= len) {
				break;
			}
			node.left = nodeArr[idx];
			if (nodeArr[idx] != null) {
				queue.add(nodeArr[idx]);
			}
			idx++;
			if (idx < len) {
				node.right = nodeArr[idx];
				if (nodeArr[idx] != null) {
					queue.add(nodeArr[idx]);
				}
			}
		}

		return nodeArr[0];
	}

	/**
	 * 根据二叉树的层序遍历列表还原二叉树
	 * 
	 * @param list
	 * @return
	 */
	public static TreeNode convertFromList(List<List<Integer>> list) {
		if (list.size() == 0) {
			return null;
		}
		Queue<TreeNode> parentQueue = new LinkedList<>();
		TreeNode root = new TreeNode(0);
		for (int level = 0; level < list.size(); level++) {
			List<Integer> childList = list.get(level);
			if (level == 0) {
				root.val = childList.get(0).intValue();
				parentQueue.add(root);
			} else {
				int parentLen = parentQueue.size();
				int childLen = childList.size();
				for (int parentIdx = 0; parentIdx < parentLen; parentIdx++) {
					TreeNode parent = parentQueue.poll();
					if (parent != null) {
						int childIdx = 2 * parentIdx;
						if (childIdx < childLen) {
							if (childList.get(childIdx) != null) {
								TreeNode node = new TreeNode(childList.get(childIdx).intValue());
								parent.left = node;
								parentQueue.add(node);
							} else {
								parentQueue.add(null);
							}
						}
						childIdx++;
						if (childIdx < childLen) {
							if (childList.get(childIdx) != null) {
								TreeNode node = new TreeNode(childList.get(childIdx).intValue());
								parent.right = node;
								parentQueue.add(node);
							} else {
								parentQueue.add(null);
							}
						}
					}
					parentIdx++;
				}
			}
		}

		return root;
	}

	public static boolean isEquivalent(TreeNode node1, Integer[] arr) {
		return isSame(node1, convertFromArr(arr));
	}

	public static boolean isEquivalent(TreeNode node1, List<List<Integer>> list) {
		return isSame(node1, convertFromList(list));
	}

	public static boolean isSame(TreeNode node1, TreeNode node2) {
		if (node1 == null || node2 == null) {
			return node1 == node2;
		}
		return node1.val == node2.val && isSame(node1.left, node2.left) && isSame(node1.right, node2.right);
	}

}